public class Solution {
    public int numDecodings2(String s) {
        //1.创建dp表
        int n = s.length();
        int[] dp = new int[n+1];//多创建一个虚拟位置dp[0]
        dp[0]= 1;

        char[] ch = s.toCharArray();
        //2.初始化
        if(ch[0] != '0') {
            dp[1]++;
        }else {
            return 0;
        }
        if(n == 1) return dp[1];

        //3.填表
        for(int i = 2; i <= n; i++) {
            if(ch[i-1] != '0') {
                dp[i] += dp[i-1];
            }

            int tt = (ch[i-2] - '0') * 10 + (ch[i-1] - '0');
            if(tt <= 26 && tt >= 10) {
                dp[i] += dp[i-2];
            }
        }

        //4.返回值
        return dp[n];
    }
    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n];
        char[] ch = s.toCharArray();
        if(ch[0] != '0') {
            dp[0]++;
        }else {
            return 0;
        }
        if(n == 1) return dp[0];
        if(ch[1] != '0') dp[1]++;
        if((ch[0] - '0') * 10 + (ch[1] - '0') <= 26 && (ch[0] - '0') * 10 + (ch[1] - '0') >= 10) dp[1]++;
        for(int i = 2; i < n; i++) {
            if(ch[i] != '0') {
                dp[i] += dp[i-1];
            }

            if((ch[i-1] - '0') * 10 + (ch[i] - '0') <= 26 && (ch[i-1] - '0') * 10 + (ch[i] - '0') >= 10) {
                dp[i] += dp[i-2];
            }
        }
        return dp[n-1];
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        int val1 = list1.val;
        int val2 = list2.val;
        if(val1 < val2) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //1.建表
        int[][] dp = new int[m][n];

        //2.初始化
        dp[0][0] = 1;

        //3.填表
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i-1 >= 0 && obstacleGrid[i-1][j] == 0) {
                    dp[i][j] += dp[i-1][j];
                }
                if(j-1 >= 0 && obstacleGrid[i][j-1] == 0) {
                    dp[i][j] += dp[i][j-1];
                }
            }
        }

        //4.返回值
        return dp[m-1][n-1];
    }
}